#include "dict.h"
#include <errno.h>
#include <stddef.h>
#include <string.h>
#include <stdlib.h>

#define MINSIZE         8
#define PERTURB_SHIFT   5

static const char * const dummy = "";

static hash_t hash(const char *s) {
    register hash_t hashval;
    for (hashval = 0; *s; s++)
        hashval = *s + 31 * hashval;
    return hashval;
}

static struct dict_entry *lookup(struct dict *dict, const char *key, hash_t hash) {
    register size_t i;
    register size_t perturb;
    register struct dict_entry *freeslot;
    register struct dict_entry *ep;
    register size_t mask = dict->mask;

    i = hash & mask;
    ep = &dict->tab[i];
    if (!ep->key)
        return ep;

    if (ep->key == dummy)
        freeslot = ep;
    else if (ep->hash == hash && strcmp(ep->key, key) == 0)
        return ep;
    else
        freeslot = NULL;

    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
        i = (i << 2) + i + perturb + 1;
        ep = &dict->tab[i & mask];
        if (!ep->key)
            return freeslot ?: ep;
        if (ep->key != dummy) {
            if (ep->hash == hash) {
                if (strcmp(ep->key, key) == 0)
                    return ep;
            }
        } else if (!freeslot)
            freeslot = ep;
    }

    return NULL;
}

static int insert(struct dict *dict, const char *key, hash_t hash,
        const void *value, const char **oldkey, const void **oldvalue) {
    register struct dict_entry *ep;

    if (!(ep = lookup(dict, key, hash))) {
        errno = ENOMEM;
        return -1;
    }

    if (!ep->key || ep->key == dummy) {
        ep->hash = hash;
        ++dict->used;
        if (!ep->key)
            ++dict->fill;
    }

    if (oldkey)
        *oldkey = ep->key;
    if (oldvalue)
        *oldvalue = ep->value;

    ep->key = key;
    ep->value = value;

    return 0;
}

static void insert_clean(struct dict *dict, const struct dict_entry *old) {
    register size_t i;
    register size_t perturb;
    register size_t mask = dict->mask;
    struct dict_entry *ep, *ep0 = dict->tab;

    i = old->hash & mask;
    ep = &ep0[i];
    for (perturb = old->hash; ep->key; perturb >>= PERTURB_SHIFT) {
        i = (i << 2) + i + perturb + 1;
        ep = &ep0[i & mask];
    }
    *ep = *old;
    ++dict->fill;
    ++dict->used;
}

static int resize(struct dict *dict, size_t size) {
    register struct dict_entry *ep;
    register size_t newsize;
    register size_t i;
    struct dict_entry *oldtable, *newtable;

    i = -1;
    i = (i >> 1) + 1;
    if (size >= i) { /* too big */
        errno = ENOMEM;
        return -1;
    }

    newsize = MINSIZE;
    while (newsize <= size)
        newsize <<= 1;

    oldtable = dict->tab;

    newtable = malloc(sizeof(*newtable) * newsize);
    if (!newtable) {
        errno = ENOMEM;
        return -1;
    }

    i = dict->mask + 1;
    dict->tab = newtable;
    dict->mask = newsize - 1;
    memset(newtable, 0, sizeof(*newtable) * newsize);
    dict->used = 0;
    dict->fill = 0;

    for (ep = oldtable; i; ++ep, --i)
        if (ep->key && ep->key != dummy)
            insert_clean(dict, ep);

    free(oldtable);

    return 0;
}

struct dict *dict_create() {
    struct dict *p;
    if ((p = malloc(sizeof(*p)))) {
        if ((p->tab = malloc(sizeof(*p->tab) * MINSIZE))) { /* default size is 8 */
            memset(p->tab, 0, sizeof(*p->tab) * MINSIZE);
            p->mask = MINSIZE - 1;
            p->used = 0;
            p->fill = 0;
            return p;
        }
    }
    free(p);

    return NULL;
}

void dict_destroy(struct dict *dict, free_cb *key_free_cb, free_cb *value_free_cb) {
    if (dict) {
        dict_clean(dict, key_free_cb, value_free_cb);
        free(dict->tab);
        free(dict);
    }
}

void dict_clean(struct dict *dict, free_cb *key_free_cb, free_cb *value_free_cb) {
    struct dict_entry *ep;
    register int i;

    if (!dict)
        return;

    for (ep = dict->tab, i = dict->mask + 1; i; ++ep, --i)
        if (ep->key) {
            if (key_free_cb)
                key_free_cb((void *)ep->key);
            if (value_free_cb)
                value_free_cb((void *)ep->value);
            ep->value = ep->key = NULL;
        }
}

/* success return 0, failed return -1 */
int dict_set(struct dict *dict, const char *key, const void *value,
        const char **oldkey, const void **oldvalue) {
    if (dict->fill * 3 > (dict->mask + 1) * 2 && resize(dict, dict->used * 2))
        return -1;
    hash_t hashv = hash(key);
    return insert(dict, key, hashv, value, oldkey, oldvalue);
}

const void *dict_get(struct dict *dict, const char *key, const char **oldkey) {
    struct dict_entry *ep;

    hash_t hashv = hash(key);
    if ((ep = lookup(dict, key, hashv)) && ep->key) {
        if (oldkey)
            *oldkey = ep->key;
        return ep->value;
    }

    return NULL;
}

void dict_del(struct dict *dict, const char *key, const char **oldkey,
        const void **oldvalue) {
    hash_t hashv = hash(key);
    struct dict_entry *ep;

    if ((ep = lookup(dict, key, hashv))) {
        if (oldkey)
            *oldkey = ep->key;
        if (oldvalue)
            *oldvalue = ep->value;
        ep->key = dummy;
        ep->value = NULL;
        --dict->used;
    }

}
